package violentRecursion;

import org.junit.Test;


public class LeetCode_688 {

    @Test
    public void test_solution_1(){
        double result = solution_1(3,0, 0, 2);
        System.out.println(result);
        System.out.println( result * 1.0 / Math.pow(8,2) );
    }

    @Test
    public void test_solution_2(){
        int n = 3;
        int x = 0;
        int y = 0;
        int k = 2;
        double[][][] memo = new double[n][n][k+1];
        //初始化记忆表
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l <= k; l++) {
                    memo[i][j][l] = -1;
                }
            }
        }
        double result = solution_2(memo,n,x, y, k);
        System.out.println( result * 1.0 / Math.pow(8,k) );
    }

    @Test
    public void test_solution_3(){
        int n = 8;
        int x = 6;
        int y = 4;
        int k = 30;

        double result = solution_3(n,x, y, k);
        System.out.println( result * 1.0 / Math.pow(8,k) );
    }

    @Test
    public void check(){
        int count = 1000; //测试次数
        int num_range = 10; //测试范围
        for (int i = 0; i < count; i++) {
            int n = 10;
            int x = (int)(Math.random() * num_range)+1; //[1,10]
            int y = (int)(Math.random() * num_range)+1;
            int power = (int)(Math.random() * num_range);
            double ways_1 = solution_1(n,x,y,power);
            double[][][] memo = new double[n][n][power+1];
            //初始化memo数组
            for (int k = 0; k < n; k++) {
                for (int j = 0; j < n; j++) {
                    for (int l = 0; l <= power; l++) {
                        memo[k][j][l] = -1;
                    }
                }
            }
            double ways_2 = solution_2(memo,n,x,y,power);
            double ways_3 = solution_3(n,x,y,power);
            if (ways_1!= ways_2 || ways_1!= ways_3){
                System.out.println("error");
                System.out.println("x="+x+",y="+y+",power="+power);
                System.out.println("ways_1="+ways_1+",ways_2="+ways_2 +",ways_3="+ways_3);
                break;
            }
        }
        System.out.println("测试完成");


    }


    public double knightProbability(int n, int k, int row, int column) {
//        return solution_1(n, row, column, k)*1.0/Math.pow(8,k);
        /*int[][][] memo = new int[n][n][k+1];
        //初始化记忆表
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l <= k; l++) {
                    memo[i][j][l] = -1;
                }
            }
        }
        return solution_2(memo,n, row, column, k)*1.0/Math.pow(8,k);*/
        return solution_3(n, row, column, k)*1.0/Math.pow(8,k);
    }


    /**
     * 方法1：暴力递归，枚举所有可能的走法，计算每种走法的步数，然后累计求和
     * @param n 棋盘大小
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public double solution_1(int n, int x,int y,int power){
        //1. 出界判断
        if(x<0 || x>=n || y<0 || y>=n){
            return 0;
        }
        //2. 终止条件


        if (power < 0){
            return 0;
        }
        if (power == 0){
            return 1;
        }
        //3. 递归计算
        double ways = 0;
        ways += solution_1(n,x-1,y-2,power-1)+
                solution_1(n,x-2,y-1,power-1)+
                solution_1(n,x-2,y+1,power-1)+
                solution_1(n,x-1,y+2,power-1)+
                solution_1(n,x+1,y+2,power-1)+
                solution_1(n,x+2,y+1,power-1)+
                solution_1(n,x+2,y-1,power-1)+
                solution_1(n,x+1,y-2,power-1);
        return ways;
    }

    /**
     * 方法2：记忆表法
     * @param n 棋盘大小
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public double solution_2(double[][][] memo, int n, int x,int y,int power){
        //1. 出界判断
        if(x<0 || x>=n || y<0 || y>=n){
            return 0;
        }
        //2. 终止条件
        if (power < 0){
            return 0;
        }
        if (power == 0){
            return 1;
        }
        //3. 记忆表搜索
        if (memo[x][y][power] != -1) {
            return memo[x][y][power];
        }
        //4. 递归计算
        double ways = 0;
        ways += solution_1(n,x-1,y-2,power-1)+
                solution_1(n,x-2,y-1,power-1)+
                solution_1(n,x-2,y+1,power-1)+
                solution_1(n,x-1,y+2,power-1)+
                solution_1(n,x+1,y+2,power-1)+
                solution_1(n,x+2,y+1,power-1)+
                solution_1(n,x+2,y-1,power-1)+
                solution_1(n,x+1,y-2,power-1);
        return ways;
    }

    /**
     * 方法3：严格表结构
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public double solution_3(int n, int x,int y,int power){
        //1. 出界判断
        if(x<0 || x>=n || y<0 || y>=n){
            return 0;
        }

        //1. 初始化严格表
        double[][][] memo = new double[n][n][power+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j][0] = 1;
            }
        }
        //2. 根据公式逐层计算
        for (int k = 1; k <= power; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {

                    memo[i][j][k] =
                            (((i-1>=0) && (j-2>=0))?memo[i-1][j-2][k-1]:0)+
                                    (((i-2>=0) && (j-1>=0))?memo[i-2][j-1][k-1]:0)+
                                    (((i-2>=0) && (j+1<n))?memo[i-2][j+1][k-1]:0)+
                                    (((i-1>=0) && (j+2<n))?memo[i-1][j+2][k-1]:0)+
                                    (((i+1<n) && (j+2<n))?memo[i+1][j+2][k-1]:0)+
                                    (((i+2<n) && (j+1<n))?memo[i+2][j+1][k-1]:0)+
                                    (((i+2<n) && (j-1>=0))?memo[i+2][j-1][k-1]:0)+
                                    (((i+1<n) && (j-2>=0))?memo[i+1][j-2][k-1]:0);
                }
            }
        }
        //3. 计算结果
        return memo[x][y][power];

    }







}
